#include <gtest/gtest.h>
#include "common.h"

using namespace ::std;

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix);
};

// 最大正方形，不是长方形！！！
// 暴力解，找支点。遍历到每一个点，都以该点为左上角，遍历搜索出可能的最大正方形。记录最大边长
// 超出时间限制
int Solution::maximalSquare(vector<vector<char>>& matrix) {
    int xLength = matrix.size(), yLength = matrix[0].size();
    int maxBorderLength = 0;
    for(int i = 0; i < xLength; ++i) {
        for(int j = 0; j < yLength; ++j) {
            int currentBorderLength = 0;
            while(i + currentBorderLength < xLength && j + currentBorderLength < yLength) {
                int k, l;
                for(k = i + currentBorderLength, l = j; l <= j + currentBorderLength && '1' == matrix[k][l]; ++l) ;
                if(l != j + currentBorderLength + 1) break;
                for(l = j + currentBorderLength, k = i; k <= i + currentBorderLength && '1' == matrix[k][l]; ++k) ;
                if(k != i + currentBorderLength + 1) break;
                currentBorderLength++;
            }
            if(currentBorderLength > maxBorderLength) maxBorderLength = currentBorderLength;
        }
    }
    return maxBorderLength * maxBorderLength;
}

class MaximalSquareCheck : public ::testing::Test {
public:
	class Solution solution;
};

TEST_F(MaximalSquareCheck, testMaximalSquare_1) {
    vector<vector<char>> matrix =  {{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};
    EXPECT_TRUE(4 == solution.maximalSquare(matrix));
}

TEST_F(MaximalSquareCheck, testMaximalSquare_2) {
    // C++ exception with description "cannot create std::vector larger than max_size()" thrown in the test body
    // vector<vector<char>> matrix =  {{"0","1"},{"1","0"}};
    vector<vector<char>> matrix =  {{'0','1'},{'1','0'}};
    EXPECT_TRUE(1 == solution.maximalSquare(matrix));
}

TEST_F(MaximalSquareCheck, testMaximalSquare_3) {
    vector<vector<char>> matrix =  {{'0'}};
    EXPECT_TRUE(0 == solution.maximalSquare(matrix));
}

TEST_F(MaximalSquareCheck, testMaximalSquare_4) {
    vector<vector<char>> matrix =  {{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};
    EXPECT_TRUE(9 == solution.maximalSquare(matrix));
}


int main() {
	::testing::InitGoogleTest();
	return RUN_ALL_TESTS();
}
